Telecommunications carriers (e.g., long distance providers) continually strive to increase the reliability of their communications networks. They do this, in part, by increasing the speed by which they can restore network operation following failure in one or more components of the network. A communications network consists of a collection of transmission links, also known as segments, that are interconnected at network nodes. The segments include transmission lines, fiber optic cables, microwave links, and other such transmission medium. Traffic is transmitted on the network from one endpoint to another endpoint through a current route or "trunk," which is a network path of segments that interconnect the endpoints. The network nodes may serve a variety of functions such as amplifying the network traffic for transmission down the next segment in the route or establishing an interconnection between two segments connected to the node (i.e., a switch). Segments are interconnected by switching nodes to form "spans." The switching nodes can be controlled locally or from a remote computer system to connect or to disconnect segments that are connected to the node.
Unfortunately, the components (e.g., nodes and segments) of the communications network may occasionally fail. For example, a segment that is a buried fiber optic cable may fail as a result of being inadvertently severed by someone digging near the buried cable. If one or more of the cables fail, massive disruption of services to a large number of network customers could result. Therefore, telecommunications carriers strive to quickly and economically route the network traffic around such failed components by establishing a "restoral" route. A restoral route is a path between the endpoints that does not include the failed component. The establishing of a restoral route generally involves: (1) detecting that a component on the current route has failed, (2) identifying the location of the component, (3) selecting a restoral route to bypass the failed component, and (4) implementing the selected restoral route. The reliability of telecommunication networks depends in large part on the ability to detect such failures and implement the restoral route with minimal impact on network customers. A plan that identifies which switching nodes, also referred to as restoration nodes, are to be switched to bypass one or more specific failed components is called a "restoration plan."
Communications networks typically have excess capacity that can be used to bypass a failed component. The segments of a network that are currently being used to bear traffic are referred to as active segments, and the segments that are not being currently used to bear traffic (i.e., excess capacity) are referred to as spare segments. Spare segments that are currently connected to another to form a span are referred to as a spare span. Restoral routes are implemented by identifying spare segments and incorporating certain of those spare segments into the network. Telecommunications carriers desire to use restoral routes that minimize costs and that can be implemented rapidly when a network failure is detected. Telecommunications carriers typically consider the quality, capacity, and length of a restoral route as an indication of the cost of the restoral route. However, other costs, such as switching costs and fragmentation costs, are typically not considered. In general, it is desirable to reduce the number of connections and disconnections (i.e., actions) when bypassing a failure. The number of connects and disconnects increases the time needed to implement a restoral route. Also, since an attempted connect or disconnect can fail, it is also desirable to reduce the number of connects and disconnects to reduce the chance of the implementation of the restoral route failing. Switching costs are the costs associated with switching a restoration node to disconnect the failed segment and to connect spare segments to the non-failed active segments. Fragmentation costs are costs associated with using only a certain portion of a long spare span as part of the restoral route. Fragmentation of spans affects cost in a couple of ways. First, there is a current cost at the time of network failure associated with disconnecting a spare segment from a spare span so that the spare segment can then be connected as part of the restoral route. Second, there is a delayed cost associated with the disconnecting of the spare segment if the spare span could have been used in the future as part of the restoral route. The delayed fragmentation cost occurs because additional connections in the future may need to be created to build a restoral route to bypass a failure that the long spare span could have bypassed before it was fragmented.